
class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    public TreeNode createTree() {
        BinaryTree.TreeNode node1 = new TreeNode('A');
        BinaryTree.TreeNode node2 = new TreeNode('B');
        BinaryTree.TreeNode node3 = new TreeNode('C');
        BinaryTree.TreeNode node4 = new TreeNode('D');
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        return node1;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root==null){
            return ;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root==null){
            return ;
        }

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root==null){
            return ;
        }

        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val+" ");
    }


    public  int nodeSize;

    public int size(TreeNode root) {//遍历
        if (root == null){
            return 0;
        }

        int leftSize = size(root.left);
        int rightSize = size(root.right);
        return leftSize+rightSize+1;
    }


    public int size2(TreeNode root) {//子问题
        if (root == null){
            return nodeSize;
        }
        nodeSize++;
        size2(root.left);
        size2(root.right);
        return nodeSize;
    }

    int getLeafNodeCount1(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }

    public int leafSize = 0;
    void getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return ;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }


    int getKLevelNodeCount(TreeNode root, int k) {
        if (root==null){
            return 0;
        }
        if (k==1){
            return 1;
        }

        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }



    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        return (getHeight(root.left) > getHeight(root.right)) ?
                (getHeight(root.left)+1):(getHeight(root.right)+1);
    }
}

public class Text1 {
        public static void main(String[] args) {
            BinaryTree node = new BinaryTree();
            BinaryTree.TreeNode rootTmp = node.createTree();
            System.out.println("前序遍历结果：");
            node.preOrder(rootTmp);
            System.out.println();
            System.out.println("中序遍历结果：");
            node.inOrder(rootTmp);
            System.out.println();
            System.out.println("后序遍历结果：");
            node.postOrder(rootTmp);
            System.out.println();
            System.out.println(node.size(rootTmp));
            System.out.println(node.size2(rootTmp));
            System.out.println(node.getLeafNodeCount1(rootTmp));
            node.getLeafNodeCount2(rootTmp);
            System.out.println(node.leafSize);
            int tmp=node.getKLevelNodeCount(rootTmp,2);
            System.out.println(tmp);
        }
    }

